class Treenode:
    def __init__(self, val):
        self.val = val
        self.neighbors = {}
        self.flag = -1


class WordFilter(object):

    def __init__(self, words):
        """
        :type words: List[str]
        """
        self.tree = Treenode(('#', '#'))
        for index, word in enumerate(words):
            m = len(word)
            cur = self.tree
            for i in range(m):
                node = cur
                for j in range(i, m):
                    key = (word[j], '#')
                    if key in node.neighbors:
                        node = node.neighbors[key]
                    else:
                        new_node = Treenode(key)
                        node.neighbors[key] = new_node
                        node = new_node
                    node.flag = index
                node = cur
                for j in range(i, m):
                    key = ('#', word[- 1 - j])
                    if key in node.neighbors:
                        node = node.neighbors[key]
                    else:
                        new_node = Treenode(key)
                        node.neighbors[key] = new_node
                        node = new_node
                    node.flag = index
                key = (word[i], word[-1 - i])
                if key in cur.neighbors:
                    cur = cur.neighbors[key]
                else:
                    new_node = Treenode(key)
                    cur.neighbors[key] = new_node
                    cur = new_node
                cur.flag = index

    def f(self, pref, suff):
        m1 = len(pref)
        m2 = len(suff)
        if m1 < m2:
            pref = pref + '#' * (m2 - m1)
        else:
            if m1 > m2:
                suff = '#' * (m1 - m2) + suff
        m = len(pref)
        node = self.tree
        for i in range(m):
            key = (pref[i], suff[-1 - i])
            if key in node.neighbors:
                node = node.neighbors[key]
            else:
                return -1
        return node.flag
